/**
 * Created with IntelliJ IDEA.
 * User:xieChao
 * Date:2022/10/7 20:51
 */
public class TreeNode {
      int val;
    TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
   TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
        this.left = left;
        this.right = right;
     }
 }
class Solution {
                           //判断两棵二叉树是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null && q != null || p != null && q == null){
            return false;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }

                             //借用上面判断两二叉树是否包含
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null || subRoot == null) return false;

        if(isSameTree(root,subRoot)){
            return true;
        }
        if(isSubtree(root.left,subRoot)){     //注意是issubtree递归isSameTree
            return true;
        }
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }


    //求二叉树最大深度
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int lefthight = maxDepth(root.left);
        int righthight = maxDepth(root.right);
        return lefthight>righthight ? lefthight+1:righthight+1;//1是加上根结点
    }


    //借助最大深度函数--去判断是否是平衡二叉树
    //时间复杂度：O(n^2)
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        return Math.abs(left-right)<=1 && isBalanced(root.left) && isBalanced(root.right);
    }

    /**
     * 优化判断平衡二叉树
     * 时间复杂度：O(n)
     * @param root
     * @return
     */
    public int maxDepth1(TreeNode root) {
        if(root == null){
            return 0;
        }
        int lefthight = maxDepth(root.left);
        int righthight = maxDepth(root.right);
        if(lefthight >= 0 && righthight >= 0 && Math.abs(lefthight-righthight)<=1){
            return Math.max(lefthight,righthight)+1;
        }else{
            return -1;
        }
    }
    public boolean isBalanced2(TreeNode root) {
        if(root == null) return true;
        return maxDepth(root) !=-1;
    }

    /**
     * 判断是否是对称二叉树
     * @param lefttree
     * @param righttree
     * @return
     */
    public boolean isSymmetricChild(TreeNode lefttree,TreeNode righttree){
        if(lefttree == null && righttree == null) {
            return true;
        }
        if(lefttree != null&&righttree == null || lefttree== null&&righttree != null){
            return false;
        }
        if(lefttree.val != righttree.val){
            return false;
        }
        return isSymmetricChild(lefttree.left,righttree.right)&&isSymmetricChild(lefttree.right,righttree.left);
    }

    public boolean isSymmetric(TreeNode root) {
        if(root == null){return true;}
        return isSymmetricChild(root.left,root.right);
    }

    /**
     * 层序遍历
     * @param root
     * @return
     */
//    public List<List<Integer>> levelOrder(TreeNode root) {
//        List<List<Integer>> ret = new ArrayList<>();
//        if(root == null) return ret;
//
//        Queue<TreeNode>queue = new LinkedList<>();
//        queue.offer(root);
//        while(!queue.isEmpty()){
//            int size = queue.size();
//            List<Integer> list = new ArrayList<>();
//            while(size != 0){
//                TreeNode cur = queue.poll();
//                list.add(cur.val);
//                if(cur.left != null) {
//                    queue.offer(cur.left);
//                }
//                if(cur.right != null) {
//                    queue.offer(cur.right);
//                }
//                size--;
//            }
//            ret.add(list);
//        }
//        return ret;
//    }

    /**
     * 最近公共祖先思路1--搜索二叉树引出
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){return null;}
        if(root == p || root == q){return root;}

        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);

        if(left != null && right != null){
            return root;
        }else if(left != null){
            return left;
        }else{
            return right;
        }
    }

    /**
     * 搜索二叉树转换成双向链表
     */
    TreeNode prev = null;
    public void inorder(TreeNode root){
        if(root == null) return;
        inorder(root.left);
        root.left = prev;
        if(prev != null){
            prev.right = root;
        }
        prev = root;
        //System.out.print(root.val+" ");
        inorder(root.right);
    }

    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        inorder(pRootOfTree);
        TreeNode head = pRootOfTree;
        while(head.left != null){
            head = head.left;
        }
        return head;
    }

    /**
     * 前序遍历转换成带括号的字符串
     * @param root
     * @param sb
     */
    public void treeToString(TreeNode root,StringBuilder sb){
        if(root == null) return;
        sb.append(root.val);
        if(root.left != null){
            sb.append("(");
            treeToString(root.left,sb);
            sb.append(")");
        }else{
            if(root.right == null){ //注意，此时的if在我if(root.left != null)前提下
                return;
            }else{
                sb.append("()");//右子树不为空,左子树为空
            }
        }
        if(root.right == null){
            return;
        }else{
            sb.append("(");//右子树不为空
            treeToString(root.right,sb);
            sb.append(")");
        }
    }

    public String tree2str(TreeNode root) {
        if(root == null) return null;
        StringBuilder sb = new StringBuilder();
        treeToString(root,sb);
        return sb.toString();
    }

    /**
     * 非递归后序遍历
     */
//    Stack<TreeNode> stack = new Stack<>();
//    TreeNode cur = root;
//    List<Integer> ret = new ArrayList<>();
//
//
//    TreeNode prev = null;
//        while(cur != null || !stack.isEmpty()){
//        while(cur != null){
//            stack.push(cur);
//            cur = cur.left;
//        }
//        TreeNode top = stack.peek();
//        //如果当前节点的右子树被打印过 或者 遍历过了 就弹出
//        if(top.right == null || top.right == prev){
//            stack.pop();
//            ret.add(top.val);
//            prev = top;//记录最近一次打印的节点
//        }else{
//            cur = top.right;
//        }
//    }
//        return ret;
//}


}
